火柴棒等式
题目 火柴棒等式
给你 n 根火柴棍，你可以拼出多少个形如 A+B=C 的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 0）。用火柴棍拼数字 0\sim9 的拼法如图所示：
注意：
- 加号与等号各自需要两根火柴棍；
- 如果 $$$A\neq B$，则 A+B=C 与 B+A=C 视为不同的等式\(（A,B,C\geq0）\)；
- n 根火柴棍必须全部用上。
输入格式
一个整数 \(n(1 \leq n\leq 24)\)。
输出格式
一个整数，能拼成的不同等式的数目。
样例 #1
样例输入 #1
14
样例输出 #1
2
样例 #2
样例输入 #2
18
样例输出 #2
9
提示
【输入输出样例 1 解释】
2 个等式为 0+1=1 和 1+0=1。
【输入输出样例 2 解释】
9个等式为
\(0+4=4、0+11=11、1+10=11、2+2=4、2+7=9、4+0=4、7+2=9、10+1=11、11+0=11。\)思路分析
枚举每个位置能放什么 可以重复 所以是指数型枚举
枚举出来一种方案后 检查是否满足上面的两个条件 cnt++
大概率会tle的 后面再想减枝 先写着
把问题想简单了 忽略了A B C都可能是两位数的情况
但是还能过2/5……
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int plans[5],cost[10]={6,2,5,5,4,5,6,3,7,6};
int n,res;
void dfs(int u){
if(u>3){
int A=plans[1],B=plans[2],C=plans[3];
if(A+B==C && cost[A]+cost[B]+cost[C]==n-4)
res++;
return;
}
for(int i=0;i<=9;i++){
plans[u]=i;
dfs(u+1);
plans[u]=-1;
}
}
int main()
{
cin>>n;
dfs(1);
cout<<res;
return 0;
}
要考虑每个数都可能是两位数的话 就比较复杂了
因为n≤24 也就是说刨去加号和等号后 可用的火柴数有20根
那就是意味着 A B C三个位置都可以取20根火柴可以组成的所有情况
在这20根火柴能组成的所有数里面做指数型枚举 而不是前面的0~9了
至于这20根火柴能组成的最大的合法的数是什么……头疼
假设能到1000吧 那就是说 每个位置上可以放0~1000（实际最大应该是711）
把总和也当成一个参数放进去 方便减枝
那么就变成了 三个位置 每一位都可能放0~1000 然后sum会+=calc(i)
这个calc还是比较好算的 因为不管ABC是多少位 所需要的火柴数都是每一位的需要的火柴数相加 而每一位需要的火柴数不外乎就是那几个（0~9所需要的火柴数） 所以可以按位来处理 计算出当前位需要的总火柴数
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int plans[5],cost[10010]={6,2,5,5,4,5,6,3,7,6};
int n,res;
int calc(int x){
if(cost[x])
return cost[x];
else{
int sumfire=0;
while(x){
sumfire+=cost[x%10];
x/=10;
}
return sumfire;
}
}
void dfs(int u,int sum){
if(sum>n-4)
return;
if(u>3){
int A=plans[1],B=plans[2],C=plans[3];
if(A+B==C && sum==n-4)
res++;
return;
}
for(int i=0;i<=1000;i++){
plans[u]=i;
dfs(u+1,sum+calc(i));
plans[u]=-1;
}
}
int main()
{
cin>>n;
dfs(1,0);
cout<<res;
return 0;
}
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int path[4],cost[N]={6,2,5,5,4,5,6,3,7,6};
int n,res;
int calc(int x){
int sum=0;
if(cost[x])
sum=cost[x];
else{
while(x){
sum+=cost[x%10];
x/=10;
}
}
return sum;
}
void dfs(int u,int sum){
if(sum>n)
return;
if(u>3){
int A=path[1],B=path[2],C=path[3];
if(A+B==C && sum==n)
res++;
return;
}
for(int i=0;i<=1000;i++){
path[u]=i;
dfs(u+1,sum+calc(i));
path[u]=-1;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
n-=4;
dfs(1,0);
cout<<res;
return 0;
}
💬 评论